// Tencent is pleased to support the open source community by making RapidJSON available.
//
// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
//
// Licensed under the MIT License (the "License"); you may not use this file except
// in compliance with the License. You may obtain a copy of the License at
//
// http://opensource.org/licenses/MIT
//
// Unless required by applicable law or agreed to in writing, software distributed
// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
// CONDITIONS OF ANY KIND, either express or implied. See the License for the
// specific language governing permissions and limitations under the License.

#ifndef RAPIDJSON_INTERNAL_STACK_H_
#define RAPIDJSON_INTERNAL_STACK_H_

#include "../allocators.h"
#include "swap.h"
#include <cstddef>

#if defined(__clang__)
RAPIDJSON_DIAG_PUSH
RAPIDJSON_DIAG_OFF(c++ 98 - compat)
#endif

RAPIDJSON_NAMESPACE_BEGIN
namespace internal {

///////////////////////////////////////////////////////////////////////////////
// Stack

//! A type-unsafe stack for storing different types of data.
/*! \tparam Allocator Allocator for allocating stack memory.
 */
template <typename Allocator>
class Stack {
public:
	// Optimization note: Do not allocate memory for stack_ in constructor.
	// Do it lazily when first Push() -> Expand() -> Resize().
	Stack(Allocator* allocator, size_t stackCapacity)
	  : allocator_(allocator), ownAllocator_(0), stack_(0), stackTop_(0), stackEnd_(0),
	    initialCapacity_(stackCapacity) {}

#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
	Stack(Stack&& rhs)
	  : allocator_(rhs.allocator_), ownAllocator_(rhs.ownAllocator_), stack_(rhs.stack_), stackTop_(rhs.stackTop_),
	    stackEnd_(rhs.stackEnd_), initialCapacity_(rhs.initialCapacity_) {
		rhs.allocator_ = 0;
		rhs.ownAllocator_ = 0;
		rhs.stack_ = 0;
		rhs.stackTop_ = 0;
		rhs.stackEnd_ = 0;
		rhs.initialCapacity_ = 0;
	}
#endif

	~Stack() { Destroy(); }

#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
	Stack& operator=(Stack&& rhs) {
		if (&rhs != this) {
			Destroy();

			allocator_ = rhs.allocator_;
			ownAllocator_ = rhs.ownAllocator_;
			stack_ = rhs.stack_;
			stackTop_ = rhs.stackTop_;
			stackEnd_ = rhs.stackEnd_;
			initialCapacity_ = rhs.initialCapacity_;

			rhs.allocator_ = 0;
			rhs.ownAllocator_ = 0;
			rhs.stack_ = 0;
			rhs.stackTop_ = 0;
			rhs.stackEnd_ = 0;
			rhs.initialCapacity_ = 0;
		}
		return *this;
	}
#endif

	void Swap(Stack& rhs) RAPIDJSON_NOEXCEPT {
		internal::Swap(allocator_, rhs.allocator_);
		internal::Swap(ownAllocator_, rhs.ownAllocator_);
		internal::Swap(stack_, rhs.stack_);
		internal::Swap(stackTop_, rhs.stackTop_);
		internal::Swap(stackEnd_, rhs.stackEnd_);
		internal::Swap(initialCapacity_, rhs.initialCapacity_);
	}

	void Clear() { stackTop_ = stack_; }

	void ShrinkToFit() {
		if (Empty()) {
			// If the stack is empty, completely deallocate the memory.
			Allocator::Free(stack_);
			stack_ = 0;
			stackTop_ = 0;
			stackEnd_ = 0;
		} else
			Resize(GetSize());
	}

	// Optimization note: try to minimize the size of this function for force inline.
	// Expansion is run very infrequently, so it is moved to another (probably non-inline) function.
	template <typename T>
	RAPIDJSON_FORCEINLINE void Reserve(size_t count = 1) {
		// Expand the stack if needed
		if (RAPIDJSON_UNLIKELY(static_cast<std::ptrdiff_t>(sizeof(T) * count) > (stackEnd_ - stackTop_)))
			Expand<T>(count);
	}

	template <typename T>
	RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) {
		Reserve<T>(count);
		return PushUnsafe<T>(count);
	}

	template <typename T>
	RAPIDJSON_FORCEINLINE T* PushUnsafe(size_t count = 1) {
		RAPIDJSON_ASSERT(static_cast<std::ptrdiff_t>(sizeof(T) * count) <= (stackEnd_ - stackTop_));
		T* ret = reinterpret_cast<T*>(stackTop_);
		stackTop_ += sizeof(T) * count;
		return ret;
	}

	template <typename T>
	T* Pop(size_t count) {
		RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
		stackTop_ -= count * sizeof(T);
		return reinterpret_cast<T*>(stackTop_);
	}

	template <typename T>
	T* Top() {
		RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
		return reinterpret_cast<T*>(stackTop_ - sizeof(T));
	}

	template <typename T>
	const T* Top() const {
		RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
		return reinterpret_cast<T*>(stackTop_ - sizeof(T));
	}

	template <typename T>
	T* End() {
		return reinterpret_cast<T*>(stackTop_);
	}

	template <typename T>
	const T* End() const {
		return reinterpret_cast<T*>(stackTop_);
	}

	template <typename T>
	T* Bottom() {
		return reinterpret_cast<T*>(stack_);
	}

	template <typename T>
	const T* Bottom() const {
		return reinterpret_cast<T*>(stack_);
	}

	bool HasAllocator() const { return allocator_ != 0; }

	Allocator& GetAllocator() {
		RAPIDJSON_ASSERT(allocator_);
		return *allocator_;
	}

	bool Empty() const { return stackTop_ == stack_; }
	size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
	size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }

private:
	template <typename T>
	void Expand(size_t count) {
		// Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
		size_t newCapacity;
		if (stack_ == 0) {
			if (!allocator_)
				ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator());
			newCapacity = initialCapacity_;
		} else {
			newCapacity = GetCapacity();
			newCapacity += (newCapacity + 1) / 2;
		}
		size_t newSize = GetSize() + sizeof(T) * count;
		if (newCapacity < newSize)
			newCapacity = newSize;

		Resize(newCapacity);
	}

	void Resize(size_t newCapacity) {
		const size_t size = GetSize(); // Backup the current size
		stack_ = static_cast<char*>(allocator_->Realloc(stack_, GetCapacity(), newCapacity));
		stackTop_ = stack_ + size;
		stackEnd_ = stack_ + newCapacity;
	}

	void Destroy() {
		Allocator::Free(stack_);
		RAPIDJSON_DELETE(ownAllocator_); // Only delete if it is owned by the stack
	}

	// Prohibit copy constructor & assignment operator.
	Stack(const Stack&);
	Stack& operator=(const Stack&);

	Allocator* allocator_;
	Allocator* ownAllocator_;
	char* stack_;
	char* stackTop_;
	char* stackEnd_;
	size_t initialCapacity_;
};

} // namespace internal
RAPIDJSON_NAMESPACE_END

#if defined(__clang__)
RAPIDJSON_DIAG_POP
#endif

#endif // RAPIDJSON_STACK_H_
